|
|
Computational complexity in graph theory
Melka, Jakub ; Kratochvíl, Jan (advisor) ; Fiala, Jiří (referee)
In the present work we study the problem of reconstructing a graph from its closed neighbourhood list. We will explore this problem, formulated by V. Sós, from the point of view of the fixed parameter complexity. We study the graph reconstruction problem in a more general setting, when the reconstructed graph is required to belong to some special graph class. In the present work we prove that this general problem lies in the complexity class FPT, when parametrized by the treewidth and maximum degree of the reconstructed graph, or by the number of certain special induced subgraphs if the reconstructed graph is 2-degenerate. Also, we prove that the graph reconstruction problem lies in the complexity class XP when parametrized by the vertex cover number. Finally, we prove mutual independence of the results
|
|
|
Graph data analysis using deep learning methods
Vancák, Vladislav ; Svoboda, Martin (advisor) ; Majerech, Vladan (referee)
The goal of this thesis is to investigate the existing graph embedding methods. We aim to represent the nodes of undirected weighted graphs as low-dimensional vectors, also called embeddings, in order to create a rep- resentation suitable for various analytical tasks such as link prediction and clustering. We first introduce several contemporary approaches allowing to create such network embeddings. We then propose a set of modifications and improvements and assess the performance of the enhanced models. Finally, we present a set of evaluation metrics and use them to experimentally evalu- ate and compare the presented techniques on a series of tasks such as graph visualisation and graph reconstruction. 1
|
|
|
Computational complexity in graph theory
Melka, Jakub ; Kratochvíl, Jan (advisor) ; Fiala, Jiří (referee)
In the present work we study the problem of reconstructing a graph from its closed neighbourhood list. We will explore this problem, formulated by V. Sós, from the point of view of the fixed parameter complexity. We study the graph reconstruction problem in a more general setting, when the reconstructed graph is required to belong to some special graph class. In the present work we prove that this general problem lies in the complexity class FPT, when parametrized by the treewidth and maximum degree of the reconstructed graph, or by the number of certain special induced subgraphs if the reconstructed graph is 2-degenerate. Also, we prove that the graph reconstruction problem lies in the complexity class XP when parametrized by the vertex cover number. Finally, we prove mutual independence of the results
|
guest ::
